Electronic circuits typically have numerous electronic components such as resistors, integrated circuits (IC), capacitors, diodes, transistors, etc. Each of these components has connection points (or pins) where that component is electrically joined to one or more other components by some sort of electrical conductor. For circuits put onto a printed circuit board (PCB), the component pins are connected with conductive strips (or traces) located on (or within) the board. In many cases, the electrical circuit is first described in a schematic diagram. The schematic will usually show the circuit components as conventional symbols (e.g., a zig-zag line for a resistor, a rectangular box for an IC, etc.) interconnected by lines joining the symbolically-represented components. Based on the components set forth in the schematic and the required electrical connections between those components, the arrangement (or placing) of the physical components on a PCB is determined. Traces are then routed between pairs of pins which must be electrically connected.
As an electronic circuit become more complex, the design of a PCB for that circuit becomes more difficult. Because of this complexity, numerous designers will often work on the same PCB design. U.S. Pat. No. 6,708,313, titled “Parallel Electronic Design Automation: Shared Simultaneous Editing” and incorporated by reference herein, describes systems and methods permitting multiple designers to simultaneously work on the same PCB design. As used therein, “designer” includes both human designers and software applications performing design functions. In at least one embodiment, a server computer maintains a PCB design, and copies of that design are located on multiple client computers. Each client is able to view the entire PCB design. As edits to that design are made at the clients, those edits are transmitted to the server as requests to edit the design. After the server performs a design rule check (DRC) to confirm a requested edit will not conflict with another edit or otherwise violate a restriction imposed on the PCB design (e.g., minimum separation between traces, etc.), the server applies the requested edit to the design. The applied edit is then broadcast to the clients for update of the PCB design copies at those clients.
Even when multiple designers simultaneously work upon the same PCB design, the process can be very time-consuming. One of the most time-consuming aspects of the design process is routing of conductive paths between the electronic components. Unlike a schematic diagram, where connection lines frequently cross one another, intersecting traces on a PCB can result in a short circuit or other undesired consequences. After all the components of a circuit have been assigned a location (or placed) on the board, connections between the pins must be routed so that only the desired electrical connections are made. In some cases, a PCB may have hundreds or thousands of pins which must be interconnected. A given route for a particular connection will often foreclose available routes for other connections. As more and more connections are routed, the available routing space is reduced, and the task of routing remaining connections becomes more difficult. Although multiple layer PCBs relieve this problem somewhat by providing more space to route connections, the task remains extremely complex. Frequently, a large number of connections will be routed before it is discovered that previously-routed connections must be “ripped up” and rerouted.
Because manual routing of a PCB by human designers consumes so much worker time, numerous algorithms have been created to automate the routing process (“autorouting”). For even moderately complex circuits, however, existing algorithms require an extremely large amount of time to route an entire PCB. Indeed, it is common for PCB designers to start an autorouting program at the end of a business day and allow the program to run all night. One possible solution to these long run times is to distribute the routing task among multiple computers. Routing programs used for design of integrated circuits (ICs) have previously been converted to operate in a distributed environment. However, the routing problems for PCBs are much different than those associated with IC routing. For example, functional components of an IC tend to be more localized than in a PCB, where it is often necessary for a trace to span the entire width and/or length of a board. This lack of localization causes difficulty in apportioning regions of a PCB design for routing, as well as problems in joining sections routed by separate designers (whether human or automated). The elements of an IC tend to be closer to the same size (at least at the transistor level), and there is often no significant cost associated with connecting conductive paths in different levels of the chip. Conversely, components placed on a PCB can have widely ranging sizes, and this size range can seriously complicate a routing problem. Moreover, manufacturing costs often dictate that “vias” connecting traces on different PCB layers be minimized. For these and other reasons, distributed autorouting approaches used for IC design are of limited value in PCB design. Indeed, many have assumed that distributed PCB autorouting will require that a new type of routing algorithm first be developed, and that existing routing algorithms cannot effectively be used by multiple computers to route a single PCB.